Dynamic programming involves solving optimization problems by determining optimized solutions of sub-problems of the original problem through combining. A simple example is the coin-changing problem: how does one make change for a specific amount using the fewest coins of a given currency? By solving sub-problems of making change for smaller amounts using the fewest coins, one can combine the sub-problems and the combination is the solution for making change for the specific amount.
The hierarchical nature of this combinatorial optimization process is supported by programming language facilities such as recursive function calls which preserve state of a problem, invoke the optimization of a sub-problem, and, once the sub-problem is solved, return to the original problem and continue with original state as preserved. This works well in non-parallel computing environments with a single processing thread.
In a parallel environment with a plurality of processing threads, these common programming language facilities are not directly applicable. Processing threads must be mapped in a time-share fashion to sub-problems, recursion may not function as expected with different threads exploring different problems in real-time. In addition, the number of sub-problems may exceed the number of threads significantly.
There exists a need for a programming model for parallelization of dynamic programming to solve combinatorial optimization problems.